package com.zsj.queue;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/3/29 17:32
 * @Description 大顶堆实现优先级队列
 * 使用完全二叉树实现大顶堆
 * 完全二叉树搜索父子索引的公式 假设根节点从0开始
 * 已知子找父节点:i>0 ,父节点索引=floor((i-1)/2) 且i不能为根节点
 * 已知父节点找子节点:left = 2i+1,right = 2i+2,且left和right都不能超出长度size
 */
@SuppressWarnings("all")
public class PriorityQueueHeap<E extends Priority> implements Queue<E> {


    Priority[] priorities;

    int size;


    public PriorityQueueHeap(int capacity) {
        priorities = new Priority[capacity];
    }

    /**
     * 采取大顶堆添加元素的方式 我们先将数据添加到数组末尾
     * 然后将它与它的父节点的优先级进行对比，若其优先级比父节点大，则替换两者位置
     * 如此反复 结束条件为 父节点的优先级比它大 或者已经到根节点
     *
     * @param value 待添加元素
     * @return 添加结果
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) return false;//数组已满不允许添加
        int child = size++;
        int parent = (child - 1) / 2;
        while (value.priority() > priorities[parent].priority()) {
            priorities[child] = priorities[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        //最终child的位置就是插入位置
        priorities[child] = value;
        return true;
    }

    /**
     * 1.交换堆顶和末尾元素 将末尾元素删除就行
     * 2.恢复大顶堆结构
     * 依次比较左右两个元素 和比较大的那个交换位置
     * 直到无法交换位置为止
     *
     * @return 队尾元素
     */
    @Override
    public E poll() {
        if (isEmpty()) return null;
        swap(0, size - 1);
        size--;
        Priority priority = priorities[size];
        priorities[size] = null;//help gc
        down(0);
        return (E) priority;
    }

    /**
     * 下潜方法
     *
     * @param parent 下潜开始位置
     */
    private void down(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int max = parent;
        if (left < size && priorities[left].priority() > priorities[max].priority()) {
            //如果左边大于了当前父节点的优先级
            max = left;
        }
        if (right < size && priorities[right].priority() > priorities[max].priority()) {
            max = right;
        }
        if (max != parent) {
            swap(max,parent);
            down(max);
        }
    }

    /**
     * 交换数组中元素的方法
     *
     * @param src 元素1
     * @param end 元素2
     */
    private void swap(int src, int end) {
        E temp = (E) priorities[src];
        priorities[src] = priorities[end];
        priorities[end] = temp;
    }

    @Override
    public E peek() {
        return (E) priorities[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == priorities.length;
    }
}
